package sort;

/**
 * @author RunningShrimp
 * @date 2021/6/9  14:09
 * @see <a href=""></a>
 */
public class InsertionSort<E extends Comparable<E>> extends BaseSort<E> {
    @Override
    public void sort(E[] array) {
        for (int i = 1; i < array.length; i++) {
            for (int j = i; j > 0; j--) {
                if (less(array[j - 1], array[j])) {
                    exchange(array, j - 1, j);
                } else {
                    break;
                }
            }
        }
    }

    public void sort1(E[] array) {
        for (int i = 0; i < array.length; i++) {
            E e = array[i];
            int j = i;
            for (; j > 0; j--) {
                if (less(e, array[j - 1])) {
                    array[j] = array[j - 1];
                } else {
                    break;
                }
            }
            array[j] = e;
        }
    }

    public static void main(String[] args) {
        Integer[] array = BaseSort.generateArray(10, 100);
        InsertionSort<Integer> sort = new InsertionSort<>();
        sort.show(array);
        sort.sort1(array);
        sort.show(array);


    }
}
